package com.bz.boot;

import java.util.Arrays;

public class Solution {

    public int stoneGameV(int[] stoneValue) {
        int[][] memo = new int[stoneValue.length][stoneValue.length];

        return func(stoneValue, Arrays.stream(stoneValue).sum(), 0, stoneValue.length - 1, memo);
    }

    private int func(int[] stoneValue, int stoneSum, int start, int end, int[][] memo) {
        if (start == end) {
            return 0;
        }
        if (memo[start][end] > 0) {
            return memo[start][end];
        }

        int ans = 0;
        int preSum = stoneValue[start];
        for (int i = start + 1; i < end + 1; i++) {
            int lastSum = stoneSum - preSum;
            if (preSum >= lastSum) {
                ans = Math.max(lastSum + func(stoneValue, lastSum, i, end, memo),
                        ans);
            }
            if (preSum <= lastSum) {
                ans = Math.max(preSum + func(stoneValue, preSum, start, i - 1, memo),
                        ans);
            }

            preSum += stoneValue[i];
        }

        memo[start][end] = ans;

        return ans;
    }
}
